//将有序数组转换为二叉搜索树 
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) 
    {
        int l=0; int r=nums.size()-1;
        TreeNode* root=process(nums,l,r);
        return root;
    }
    TreeNode* process(vector<int>& nums,int l,int r)
    {
        if(l>r) return nullptr;
        int mid=(l+r)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=process(nums,l,mid-1);
        root->right=process(nums,mid+1,r);
        return root;
    }

};
//把二叉搜索树转变为累加树
class Solution {
public:
    //
    int sum=0;
    TreeNode* convertBST(TreeNode* root) 
    {
        if(root==nullptr) return nullptr;
        dfs(root);
        return root;
    }
    void dfs(TreeNode* root)
    {
        if(root==nullptr) return;
        dfs(root->right);
        sum+=root->val;
        root->val=sum;
        dfs(root->left);
    }
};

//对称二叉树
class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(!root) return true;
        return process(root->left,root->right);
    }
    bool process(TreeNode* p,TreeNode* q)
    {
        if(!p&&!q) return true;
        if((p && !q) || (!p&& q)) return false;
        if(p->val != q->val) return false;
        return process(p->left,q->right) && process(p->right,q->left);
    }
};
//二叉树的最大深度
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        if(!root) return 0;
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
};
//二叉树的最小深度
class Solution {
public:
    int minDepth(TreeNode* root) 
    {
        if(!root) return 0;
        int left=minDepth(root->left);
        int right=minDepth(root->right);
        if(!root->left && !root->right)
        {
            return 1;
        }
        if(!root->left && root->right)
        {
            return 1+right;
        }
        if(root->left && ! root->right)
        {
            return 1+left;
        }
        return 1+min(left,right);
    }
};
//完全二叉树的节点个数
class Solution {
public:
    int countNodes(TreeNode* root) 
    {
        if(!root) return 0;
        TreeNode* left=root->left;
        TreeNode* right=root->right;
        int lh=0;
        int rh=0;
        while(left)
        {
            lh++;
            left=left->left;
        }
        while(right)
        {
            rh++;
            right=right->right;
        }
        if(lh==rh)
        {
            return pow(2,rh+1)-1;
        }
        return countNodes(root->left) + countNodes(root->right)+1;
    }
};
